\chapter{Background and Literature Review}

\section{Recommender Systems}
\label{recommender}
Recommender systems are developed to assist the user with the selection of items that they might be interested in. The abundance of variety of music available on the internet has made the music recommender system an essential tool for music listeners to find music of their choice in large collections. According to \cite{schwartz} 'more is less' because when confronted with too many choices, often consumers become dubious and find themselves in the state of ``analysis paralysis" which refers to indecisiveness caused by too many options. 

\subsection{Formalisation of the Recommendation Problem}
The recommendation problem inherits prediction problem. When formalising the recommendation problem, one should first formalise the prediction problem \cite{OC10}.\\
Let, $U = {u_{1}, u_{2}, ... u_{m}}$ be the set of all users, and let $I = {i_{1}, i_{2}, ... i_{n}}$ be the set of all possible items that can be recommended. Each user $u_{i}$ has a list of items $I_{u_{i}}$ that the user is interested in, where $I_{u_{i}}$ $\subseteq$ $I$ and $I_{u_{i}}$ can be empty. Then function $P_{u_{a}, i_{j}}$  is the predicted likeliness of item $i_{j}$ for the active user $u_{a}$, such that $i_{j}$ $\notin$ $I_{u_{a}}$. This is due to the fact that the user's already mentioned interest items should not be recommended to her. Rather the items recommended should be relevant but not the same.\\
The recommendation problem is reduced to bringing a list of N items, $I_{r}$ $\subset$ $I$, that the user will like the most (i.e. the ones with higher $P_{u_{a}, i_{j}}$ value). The recommended list should not contain items from user's interests, i.e. $I_{r}$ $\bigcap$ $I_{u_{i}}$ = $\emptyset$.\\
The space for $I$ items and $U$ users can be very large. In most recommender systems, the prediction function is usually represented by a rating which is stored as a triple $<u, i, r>$ where r is the value assigned explicitly or implicitly by the user $u$ to a particular item $i$. Usually, this value is a real number (e.g. from 0 to 1), a value in a discrete range (e.g. from 1 to 5), or a binary variable (e.g. like/dislike).\\
The most popular families of recommendation strategies to solve the recommendation problem are as follows:

\subsubsection{Collaborative Filtering}
Collaborative Filtering is a widely used approach to solve the recommendation problem. The goal of this recommendation strategy is to return items with highest estimated ratings based on user's previous ratings for items \cite{1423975}. The information or patterns are extracted using stored explicit or implicit interaction between the users of the system and item set involving collaboration among multiple agents. This helps generate informed guesses for recommendations such as Amazon uses purchase history of the users and recommends items based on the purchase patterns of users with similar purchases. There are many disadvantages of using collaborative filtering such as the cold start problem in which the user cannot be recommended many relevant items unless there are enough user profiles that contain sufficient information to relate to its neighbours. There is also a new item problem, when there is no similar items to relate to a newly added item. Also, there exists sparsity problem which refers to a situation that transactional data are lacking or are insufficient. The problem to recommend items to indifferent users is also unresolved as the recommendations are not in accordance with the user's unique taste. It is easy to attack, if a group of members want to exploit the system. The solution proposed by \cite{Massa} deals with this issue by creating a trust relationship among users but it makes the system much more complicated and crowd wisdom is lost. The user's explicitly rated trust solution in FilmTrust \cite{1593032} which burden the user as the users usually have few trusted links. Online social networks platform can be useful in this regard where the `trust' relationship has already been established between the users such as on LinkedIn. 
\subsubsection{Content-based Filtering}
The content-based filtering collects items information and based on user preferences filters the results that the user is most likely to prefer.  It simply depends on item description rather than the user ratings. Content filtering is the most commonly used group of methods to filter spam. Content filters act either on the content, the information contained in the mail body, or on the mail headers (like ``Subject:") to either classify, accept or reject a message. Consequently, the most relevant emails are then filtered into Inbox and rest are stored in Spam folder for some time, in case if the system has delivered some relevant information user might want to view late.

\subsubsection{Context-based Filtering}
As the name signifies, the context-based filtering approach uses the contextual information such as geographical locations, date published, etc. to describe the items.

\subsubsection{Demographic Filtering}
The demographic filtering uses stereotyping. It filters the results based on stereotypes of users whose interest items are mostly liked. 

\subsubsection{Hybrid Filtering}
It is simply the combination of two or more recommendation strategies.

\subsection{Music Recommender System}
Music is inherently different than other types of media. The space of recommended items is extremely large e.g. a typical online music store may offer 10 million titles to chose from. Interaction with music is also different than from other types of media. People enjoy listening to same music repeatedly which is not the case for other recommendable items such as books. Listeners vary their music preference based upon context and activities. A playlist for jogging is likely to be very different than a playlist created by the same user for relaxing. Listeners enjoy listening to sequences of songs often getting as much enjoyment from the song transitions as from the songs themselves. The uniqueness of music as recommendation domain present challenges not seen in other recommender domains. It is important to consider the special nature of music when building recommenders for music. Music Recommender System have become increasingly popular because people face difficulty to find their preferred music in the huge volume of music content and music-related information available these days. As a result of continued efforts, the quality of these systems has improved over time. However, more research in this area is required for coping with the dynamic world of web. 

In \cite{barrington2009smarter}, Barrington et al. compare the Genius recommender system with a recommender based solely on acoustic similarity, one based on artist similarity and random. They evaluate the three recommenders by doing playlist generation, a user is presented with a seed song which he rates on a 5 point scale, then he is presented with two playlists generated from either of the four recommenders and can remove songs that do not fit into the playlists in relation to the seed song and rate the playlists on a 5 point scale. The user is then asked to compare the two playlists by stating which is better. They experimented by both displaying and hiding the song name and artist. The results showed that seeing song and artist names has a significant effect on how a playlist is evaluated, indicating that recommender systems must be designed with applications in mind. They found that while Genius performs as well or better than the metadata and content-based systems on their test collection of popular music, it is unable to make recommendations from the long tail of new and undiscovered music.

In \cite{fields2009analysis} Fields et al. study the social network of musicians in MySpace. They use complex network theory and audio content analysis. They show that the artist network topology is related to music genres by clustering the network into communities based on the topology and tags. They show that the artist social graph and the acoustic dissimilarity matrix encode different relations. They conclude that these two relations are different sources for music recommenders.

In \cite{levy2009music}, Levy et al. describe a music retrieval system based on both social tags and audio content. Last.fm uses a combination of collaborative filtering and analysis of user-supplied tags for artists, albums and tracks. They analyse tag data from 5265 artists and show that one third have no tags for any of their tracks and another third have around 5 tags per track on average. This shows that tagging alone can not be used in a recommendation system, because of the cold start problem. They extract muswords for a track by identifying musical events within it, and then discretising timbral and rhythmic features for each region found. They combine tag data and muswords in a vector space and provide with an analysis of results using different parameters and various types of muswords.

In \cite{shardanand1995social}, Shardanand et al. introduce social information filtering and describe its implementation in a system called Ringo which started to make personalized music recommendations in July 1994. Social information filtering makes use of users' ratings to recommend items to each other. They propose and evaluate four algorithms, namely: the mean square differences algorithm, the Pearson r algorithm, the constrained Pearson r algorithm, and the artist-artist algorithm. According to their results, the constrained Pearson r algorithm, which takes into account the positive and negative correlations, performed best in terms of number of correct recommendations performed. The artist-artist and mean square algorithms performed better in terms of quality of the recommendations but provided less recommendations. They also report on qualitative aspects of Ringo, mainly stating that feedback from users changed over time going from saying that the recommendations were ``poor" to saying that the recommendations were ``amazing" as the data pool expanded. 

Bogdanov et al. \cite{bogdanov10} present three different approaches to content-based recommendation based on musical dimensions such as genre and culture, moods and instruments, and rhythm and tempo extracted from audio features. They compare with recommendations from Last.fm in a user evaluation with 11 users. They expect the proposed approaches to be suitable for music discovery in the long tail which has a lack of contextual information, and incorrect or incomplete metadata.

In \cite{herrera10}, Herrera et al. analyse temporal patterns in users listening history. They use playcounts from last.fm to find patterns in the selection of artists or genres for certain moments of the day or for certain days of the week. They show that for certain users what to play at the ``right" moment is predictable and could be used in recommendation systems.

%Tomasik et al. \cite{tomasik2009using} show that using linear regression performs better than using sum or max when combining multiple data sources for music information retrieval. They combine data from text mining web documents to extract tags, content-based audio analysis to find acoustic features, and collaborative filtering. They run their experiment on a set of 10 thousand songs and use Pandora dictionary as ground-truth.

Aman et al.\cite{aman10} give a review of explanations, visualizations and interactive elements of user interfaces in music recommendation systems. They present a taxonomy of dimensions, namely : transparency, scrutability, effectiveness, persuasiveness, efficiency and trust. They measure recommendation aids across multiple systems according to these dimensions. Pandora and Amazon are the systems with the most recommendation aids.

\subsection{The long tail}
In \cite{levy10}, Levy et al. present their work in driving the Last.fm recommendations towards items from the long tail to remove the popularity bias. They show that there is no evidence that recommendations and radio cause a systematic bias towards more popular artists. They built a prototype recommender for long tail artists using item-based collaborative filtering with both scrobbles and tags. Their results suggest that the influence of such a recommender on users' general listening may be limited.

Lee\cite{lee10} et al. propose a collaborative filtering recommendation algorithm which removes the popularity bias. In fact recommendations from collaborative filtering often lead to "obvious" recommendations as most popular songs are the ones recommended. Their solution is to recommend songs coming from the long tail of "expert" users and novel to the user. They evaluate their algorithm by producing a page of recommendations for Last.fm users and contacted them by private message. After seeing the page, the user is asked to rate the list of recommendations on how much they liked them and how much novel they were. The survey was completed only by 11 users and show that the recommended items were mostly novel and relevant.

In \cite{gaffney2009making}, Gaffney et al. study the use of folksonomies for music discovery by users of social networking sites as a mean to discover items from the long tail. They examined in this project are MySpace, Lastfm, Pandora and Allmusic. They conducted interviews and questionnaires by contacting people outside concerts, directly on social networking sites and independent record companies. Although participants use social networking sites for music discovery, they found that people are still not using tags for discovery very much and that the ones who tag do it for personal future retrieval. 

\subsection{Recommender System and Social Web} 
The exponential growth of the social web continues to pose challenges and opportunities for recommender systems. The social web has turned information consumers into active contributors creating massive amounts of information. Finding relevant and interesting content at the right time and in the right context is challenging for existing recommender approaches. At the same time, social systems by their definition encourage interaction between users and both online content and other users, thus generating new sources of knowledge for recommender systems. Web 2.0 users explicitly provide personal information and implicitly express preferences through their interactions with others and the system (e.g. commenting, friending, rating, etc.). These various new sources of knowledge can be leveraged to improve recommendation techniques and develop new strategies which focus on social recommendation. The Social Web provides huge opportunities for recommender technology and in turn recommender technologies can play a part in fuelling the success of the Social Web phenomenon.

\subsection{Social Music Recommender System}
The strengths of social media are appreciated widely. A quantitative survey and qualitative interviews conducted by Baker et al. revealed that social networking websites could generate a strong future for the distribution of music \cite{baker2009social}. The study conducted on MySpace shows that both artists and consumers react positively towards distribution and discovery of new music through social media platforms. Laplante in \cite{laplante2010role,laplante08} presents a prelimanary study of music discovery within a population of young adolescents. She reports on a social network analysis based on interviews of 6 participants. All participants affirmed that changes in their music taste reflects changes in their social network. The analysis revealed that music opinion leaders were perceived as  good communicators, who are highly invested in music, and who are willing to share the information with their friends, three of the participants identified themselves as opinion leaders. The exchange of music information strengthens relationships. Most participants recognize their parents or one of their parents to be very influencial in terms of music discovery. Also, \cite{tepper2009pathways} found that social networks are the main source for music discovery for college students. They conclude that technology will be used to reinforce existing social patterns and relationships, rather than transform them. Therefore, while designing new software systems social music recommendations should be taken into account.\\
Web Music Communities (WMC) like Last.fm\footnote{\url{http://www.last.fm}}, Pandora\footnote{\url{http://www.pandora.com}} and Ping\footnote{\url{http://www.apple.com/itunes/ping}} are playing vital role in helping music listeners to build relations with similar music-listeners, get recommendations based on their current music collections and much more. All the music recommendation systems make use of the user provided information in order to generate relevant recommendations upon the information available. If music recommender systems take into account the social aspect of the music then it is possible to tailor music listener's socially influenced music taste. A successful attempt to model the user intentions and its extraction may further be applied in other relevant areas.\\
The existing recommendation techniques such as content-based, collaborative filtering or hybrid techniques focus on users explicit contact behaviors but ignore the implicit relationship among users in the network. It is important to realise the significance of relationships in social networks. Due to the higher expectation of users, online dating networks are trying to adopt recommender systems. A social matching system that uses past relations and user similarities in finding potential matches. Empirical analysis on the dataset collected from an online dating network shows that the recommendation success rate has increased to 31\% as compared to the baseline success rate of 19\% \cite{ICDMW} when the social aspect is taken into consideration. Similar improvements might be acheived when user's music collections are integrated into social platforms for example, Google provides music storage solution for music fans, unlike Facebook that does not provide its user with the feature of sharing music collection\footnote{\url{http://evolver.fm/2011/07/06/5-ways-google-could-steal-music-fans-from-facebook/}}. If music collection are made visible and searchable on Social Networks like Google+\footnote{\url{https://plus.google.com/}} and Facebook, it could be used as a way to introduce people to each other, work on creating DMCA-compliant streams that would allow people to listen to each other’s taste, and use taste-combining algorithms to create stations out of multiple accounts created on services like Music Beta by Google\footnote{\url{http://music.google.com/}}.\\
Comparison of Apple's Genius music recommender system with recommender systems based on acoustic similarity, artist similarity and random showed that Genius performs similar or better than the metadata and content-based recommender systems on user's test collection of popular music. But the drawback of such systems are that it is unable to make recommendations from the long tail of new and undiscovered music \cite{barrington2009smarter}. This study also reveled that seeing song and artist names has a significant effect on how a playlist is evaluated.

%Although, there is a strong bias toward audio-based approaches as most MIR researchers have strengths in signal processing in the music information retrieval community such as MIREX and MIR \cite{MIR}. The importance of music social aspects are also considered important by many musicologists and scientists \cite{Laplante08}, \cite{}

\section{Social Tagging in Music Recommendation and Discovery}

\subsection{Social Tags}
Social tags are free text labels assigned by users to resources. It does not account for controlled vocabulary as in case of keyword assignment. A typical tag is a word or short phrase that describes the resource. It is used to facilitate searching for items, exploring for new items, finding similar items, and finding other users with similar interests.

\subsection{Tagging Music}
The process of assigning tags to resources  or items (such as artists, albums, songs, etc.) is called tagging. Tagging is different from expert classification\footnote{Expert classification requires construction of an expert knowledge base in a classification task.}. Tagging is usually performed by non-expert. Whereas, in case of expert classification, the classification must be performed by experts. Loosening this restriction does not necessarily mean that tagging will perform better classification than the expert classification but it opens the door for crowd sourcing for labeling large collections of resources otherwise, cumbersome task. Thus, the advantage of using tags become visible when the tags are collectively shared and used, this phenomena is referred to as a folksonomy. Tagging has been used successfully to organize music on large music communities such as Last.fm. Tags reveal a great deal of information about genre, mood, instrumentation, and quality. Therefore, it has received great attention from Music Information Retrieval researchers. Tags are a source of human-generated contextual knowledge about music that may help resolve many MIR problems \cite{lamere2008social}. It has been applied in music information retrieval problem of genre classification where there is no strict boundaries between different genres. For example, Last.fm successfully uses collaborative tagging system to display item i.e. album/artist/track of interest to the users with several tags that represent various aspects of the same of item which is not possible with traditional genre classification systems such as used by iTunes music store.

While tagging, different people use different descriptors for resources which lead to many tags for single resource. There is usually no restriction on the number of tags that can be assigned to an item. These tags are generally assigned by a non-expert for their own personal use, such as for personal organisation or to assist with future retrieval. Therefore, generating irrelevant information and noise in the tags.

\subsection{Motivation for Tagging}
Lamere \cite{lamere2008social} reviews social tagging for music information retrieval. The motivation for tagging are described as below:

\paragraph{Memory and Context}{Tagging is used for personal retrieval of item(s). It can sometimes be frustrating as Last.fm does not let you listen to tagged songs that are not in the Last.fm catalog. Whereas, at the time of tagging it on Last.fm personalised radio, the system does not indicate this at the time of tagging.}

\paragraph{Task Organisation}{Tagging can be used for music discovery e.g. `Check out' and `New CD' are some of the example tags people use to organise music discovery tasks.}

\paragraph{Social Signaling}{Tags are a quick snapshot of one's music taste. Items tagged with `Seen Live', `Wishlist' are some of the example tags people use to show-off music taste.}

\paragraph{Social Contribution}{Tagging can be used to add to group knowledge e.g. `Not Metal '  is an example of tag people use to indicate that the item is not heavy metal.}

\paragraph{Play and Competition}{Tagging can be done by users as a result of a fun activity such as playing game and competition such as in Tag a Tune, Major Miner and Listen Game.}

\paragraph{Opinion Expression}{Tagging can be used for personal opinion regarding an item such as `Favourite', `Awesome', etc.}

\paragraph{Easy and Pleasurable}{Similar to illegal downloading of songs, tagging is also very popular for the same reason- `it is easy'. It is also a pleasurable experience to individuals.}

Tagging overcomes the problem of being definitive about single label selection due to the reason that it has to fit perfectly to resource definition to enhance searchability. Whereas, multiple tag selection for same resource can significantly increase the resource being more searchable with relevant terms.
Like other collaborative filtering techniques, tagging also suffers from cold start problem. The analysis of tags revealed that out of 280,000 artists only 21,000 artists had at least one tag out of 122,000 unique tags. Therefore, using tagging for indexing can result in leaving a huge amount of data un-indexed. Tagging games and auto-tagging are proposed solutions to solve these two problems. Other problems are synonymy, polysemy and noise where people tag with different terms for the same concepts or misspelling. Hacking is another issue where people tag with the malicious purpose of controlling the system behavior, such as for instance tagging a new band with popular tags to increase the popularity of the band. Tagging is bias as most taggers are young people and the tag space reflects the interest of the taggers population and not the general population. Although, tagging poses many problems, it is an interesting opportunity for music information retrieval research, namely regarding: expanding the tag coverage, using tags for discovery and improving the tag quality. What interests us in this thesis are questions regarding discovery, Lamere lists:

\begin{itemize}
\item How can we build an interface that exploits social tags to give a listener a more intuitive understanding of the interrelations between the many genres, styles and moods found in music?
\item How can we use social tags to bridge the semantic gap, to allow listeners to find music by describing
the music they like using words?
\item How can we use social tags to give transparent explainable recommendations?
\item How many social tags are enough before they can be used meaningfully for recommendation and discovery?
\end{itemize}

Turnbull et al. \cite{turnbull2008design, turnbull2009combining} built a semantic music discovery engine based on both tags and audio content similarity. A tagging game was designed for users to tag songs. The data collected from the tagging game was then compared with data collected from surveys and online music sites. To solve the cold start problem they developed an auto-tagging system based on audio analysis which was trained using the data collected in the tagging game. The resulting discovery engine prototype, named CAL, enables for query-by-description music search and radio playlist generation. Although, it is claimed that the system enables music discovery, it has not been evaluated.

In \cite{mesnage10}, Mesnage et al. investigated the generation of tag clouds using Bayesian models to test that social network information is better than overall popularity for ranking new and relevant information. They proposed three tag cloud generation models based on popularity, topics and social structure. They conducted two user evaluations to compare the models for search and recommendation of music with social network data gathered from Last.fm. The survey showed that search with tag clouds is not practical whereas, recommendation is promising. The performance comparison of the models shows statistically significant evidence at 5\% confidence level that the topic and social models outperform the popularity model.

Fields\cite{fields10} et al. use topic models on tags to generate playlists. They use Latent Dirichlet Allocation as topic models. From the extracted topics they generate playlists that are across genres but related. They do not provide with human evaluation of the generated playlists. Sordo\cite{sordo10} et al. propose a mechanism to organize music tags with semantic facets. They use wikipedia terms structure to categorize tags from Last.fm. 

\subsection{Visual representations}

\paragraph{Tag Cloud}{A tag cloud displays a cloud of tags sorted alphabetically and with the size proportionate to the frequency of its usage.  Tag clouds are frequently used on the web. It helps user to judge what can be expected from a web service. Tag clouds are helpful in navigation. It enables the exploration of large collections of resources. A tag cloud, as shown in Figure \ref{tag_navigation}, displays a set of tags arranged alphabetically and shown with a size relative to their usage. When a user clicks on a tag from the tag cloud, the system adds the tag to the query, the list of selected keywords. The page is redisplayed and shows relevant items to the new query and a new tag cloud of related tags to continue the navigation. The list of selected keywords can be managed by the user by removing tags or adding new ones by using the tag cloud.}

\begin{figure}[htbp]
	\centering
		\includegraphics[width=.8\textwidth]{Figures/tag_navigation.pdf}
	\caption{Tag Cloud Navigation.}
	\label{fig:tag_navigation}
\end{figure}

In \cite{Fokker:2006} tag clouds are used as navigation tool for Wikipedia\footnote{\url{http://www.wikipedia.org/}}. User can select different views based on recent tags, popular tags, personal tags or friends tags. They display related tags when the user moves the mouse over on a tag in the tag cloud. But the limitation of their approach is that related tags are not generated on multiple tags queries.

One of the very early attempts to use tagging for organising resources can be found in \cite{Keller:1997}. Keller et al. presented the first social bookmarking system called Webtagger. It enables users to assign tags to bookmarks and share it. Users need to redirect their proxy through Webtagger to install it, then buttons are displayed on the top of each page browsed, namely categorise, retrieve, view, comment and help. The approach is novel compared to storing bookmarks in the browser's folder. Bookmarks are categorized rather than saved in a single folder. They argue that hierarchical browsing is tedious and frustrating when information is nested in several deep layers. 

Dogear social bookmarking application \cite{Millen:2006a} introduced a different interface design. The main page displays the popular tag cloud and individual user pages display personalised tag clouds. Users can browse other user's bookmark collection by clicking on their username. Bookmarks collections can also be browsed by clicking on a tag. They analyse the log files to find empirical evidence that social tags improve social navigation. The study showed that most browsing activity of the web site was done through exploring people's bookmarks and then tags. They compared most browsed 10 tags with the most applied 10 tags. Both had a strong correlation but it is not clear how their findings show that tagging improves social navigation.

In \cite{Ishikawa:2007} Ishikawa et al. study the navigation efficiency when browsing users' bookmarks. The idea is to decide which user to browse to discover information. But not much light is shed on how to select tags to improve navigation.

In \cite{Li:2007} Li et al. proposed various algorithms to browse social annotations in a more efficient way. They extracted hierarchies from clusters and proposed browsing social annotations in a hierarchical manner and on temporal basis. Hierarchical browsing might not lead to more efficiency than tag cloud based navigation as hierarchical structures are not consistent. Moreover, the study is limited to sub-tags or related tags to one tag at a time and needs further evaluation on multiple tags. 

In \cite{Hearst:2008}, Hearst et al. discuss the value of tag clouds. They convey the results of two qualitative studies. They conducted 20 interviews of people who are active in web design and/or information visualization. They wondered in which way people thought the tag clouds as being useful, answers contained showing trends, seeing change of information, the availability of tags on the site, get the gist of the site, being playful, fun or inviting. Another use of tags is for self-reflection for people looking at their own tag clouds. Their second study is a web page analysis, they sampled pages returned by the Google search engine when searched for ``tag clouds" usability, trends and navigation. They categorised the discussions into 20 categories. They quote the discussions to show different opinions on the negative aspects of tag clouds, the popularity or faddishness, the role of navigation, the impact on and reception by new users, trends and tag cloud data as social data.

Rivadeneira et al. in \cite{Rivadeneira:2007} propose a paradigm for evaluating tag clouds and give guidelines for tag cloud construction. They identify tasks tag clouds can support, namely search, browsing, impression formation or gisting, and recognition/matching. They differentiate tag cloud features as text features and word placement. Text features concern the font weight, size and color, whereas word placement is affected by sorting, clustering and spatial layout. Their first experiment was conducted on 13 participants, the goal was to examine the recall from visualizing a tag cloud. People were presented with tag clouds of thirteen words from psycholinguistic database positioned randomly and with different font sizes. People recalled better words with larger font size. The second experiment tested the effect of font size and word layout on impression formation, they displayed four types of tag clouds sorted as sequential - alphabetical, sequential - frequency, spatial and list by frequency. People again recalled better words with larger font size, the layout had no effect on recognition, there was a moderate effect of layout on impression formation where the tags displayed as a list ordered by frequency resulted in a better identification of the categories.

Halvey et al. \cite{Halvey:2007} conducted an experiment to evaluate the time taken to find a particular tag in lists represented with different layouts. They presented people with lists of 60 countries and the task was to find the one asked for. They found that horizontal alphabetical lists perform better at this task followed closely by vertical alphabetical lists and alphabetical tag clouds.

Sinclair et al. in \cite{Sinclair:2008} conduct a study to examine the usefulness of tag clouds for information seeking. They asked participants to perform information seeking tasks on a folksonomy like dataset. They provided them with an interface consisting of a tag cloud and a search box. The folksonomy was created by the same participants who were asked to tag ten articles at the beginning of the study, leading to a small scale folksonomy much like the ones which could be found in small organizations or enterprises. The tag cloud displayed 70 terms in alphabetical order with varying font size proportional to the log of its frequency, they give the following equation : 

\begin{equation}
	TagSize = 1+C \frac{log(f_i-f_{min}+1)}{log(f_{max}-f_{min}+1)}
\end{equation}

$C$ corresponds to the maximum font desired, $f_i$ to the frequency of the tag to be displayed, $f_{min}$ and $f_{max}$ to the minimum and maximum frequencies of the displayed tags. Clicking on a tag of the tag cloud brings to a new page listing articles tagged with the clicked tag and a new tag cloud of co-occurring tags, clicking again on a tag restricts the list to the articles tagged with both tagged and so on. The search is based on a TF-IDF ranking. Participants were asked 10 questions about the articles and then to tell if they preferred using the search box or the tag cloud and why. They found that the tag cloud performs better when people are asked general questions, for information-seeking, people preferred to use the search box. They conclude the tag cloud is better for browsing, enhancing serendipity. The participants commented that the search box enables for more specific queries.

In \cite{Hassan-Montero:2006}, Hassan-Montero et al. propose an improvement of tag clouds by displaying them by similarity. They use the Jacard coefficient as measure of similarity, known as the relative co-occurrence. The relative co-occurrence is the division between the number of resources in which tags co-occur and the number of resources in which appear any one of two tags. If $A$ and $B$ are the resources tagged by two tags, the relative co-occurrence is :

\begin{equation}
	RC(A,B) = \frac{|A\cap B|}{|A\cup B|}
\end{equation}

They define a usefulness metric to select which tags to display in the tag cloud as the sum of the log of the frequency of a tag applied to a resource divided by the square of the number of tags assigned to the resource. The standard popularity metric being the sum of the frequency applied to resources for a tag. Their method provide little improvement on the coverage of the selected tags. The tag cloud layout is based on the similarity coefficient. The authors do not provide an evaluation of the tag cloud.

Kaser et al.\cite{Kaser:2007} propose a different algorithm for tag cloud drawing. Their methods concern how to produce the HTML in various situations. They also give an algorithm to display tags in nested tables. They do not provide evaluation regarding the usefulness of the new visual representations.

\subsection{Tagging incentives}

Golder et al. \cite{Golder:2006a} were the first to show that tag data follows a power law. They give a taxonomy of tagging incentives and look at convergence of tag descriptions of resources in \emph{del.icio.us}.

In \cite{Sen:2006}, Sen et al. examine factors that influence the way people choose tags and the degree to which community members share a vocabulary. The three factors they focus on are personal tendency, community influence and the tag selection algorithm. They give five main dimensions for the tagging design space of a social tagging system, tag sharing where users are shown other people's tags, tag selection as the method a system uses to select tags to display on the screen, item ownership where people can tag other people's items, and tag scope as broad where a tag application is a (user, item, tag) triple or narrow where tag applications are (item, tag) tuples. Other dimensions concern constraints on the creation of tags, if a tag can contain spaces or special characters, what are tag delimiters. Their study focuses on the MovieLens system which consists of user reviews of movies. They categorize tags in three categories, factual tags, subjective tags and personal tags. They divided users of the system and assigned each group a different user interface, the unshared group would not see the community tags, the shared group saw tags from their groups using a random selection algorithm, the shared-pop displayed the most popular tags, and the shared-rec group used a recommendation algorithm. The recommendation algorithm selects tags that are most commonly applied to both the target movie and to the most similar movies. They find that habit and investment influence user's tag applications, that community influence affects a user's personal vocabulary. The shared group produced more subjective tags, some factual and a few personal; the shared-pop lead to more factual tags, a few subjective and personal; the shared-rec produced more factual tags some subjective and some personal. They also conducted a user survey in which they asked users to tell for which task they thought tagging was useful, self-expression(50\%), organizing(44\%), learning(23\%), finding(27\%), and decision support(21\%).

\cite{Marlow:2006,Marlow:2006a} Marlow et al. propose a model of social tagging. Tags are associations between resources and users. They define a taxonomy of different aspects in the design of tagging systems that influence the  content and usefulness of tags, namely tagging rights (who is allowed to tag?), tagging support (blind tagging, viewable tagging, suggestive tagging), aggregation (bag-model, set-model), type of object (e.g., web pages, images etc.), source of material (by participants, by the system, any web resource), resource connectivity (linked, grouped or none), social connectivity (linked, grouped or none). They also propose aspects of user incentives expressing the different motivations to tag, future retrieval, contribution and sharing, attract attention, play and competition, self presentation, opinion expression. 

\subsection{Social dynamics}

\cite{Cattuto:2006,Cattuto:2007,Cattuto:2007a} Cattuto et al. make an empirical study of some tag data from del.icio.us and find that the distribution of tags other time follows a power law distribution. More specifically they find that the frequency of tags obey a Zipf's law which are "characteristic of self-organized communication systems and is commonly observed in natural languages and written text". They reproduced the phenomenon by using a stochastic model, leading to a model of user behavior in collaborative tagging systems. 

\subsection{Tag quality}

In \cite{Sen:2007}, Sen et al. question tag quality. Tagging systems must often select a subset of available tags to display to users due to limited screen space. Knowing the quality of tags helps in writing a tag selection algorithm. They conduct a study on the MovieLens system, this system collects movie reviews from users. They added in the interface a mechanism for users to rate the quality of tags. They experimented with multiple rating interfaces. All tags can not be rated, therefor they look for ways of predicting tag quality, based on aggregate user behavior, on a user's own ratings and on aggregate user's ratings. They find that tag selection methods that normalize by user, such as the numbers of users who applied a tag, perform better.

Von Ahn in \cite{Ahn:2005} tackles the problem of tag quality by having people guessing tags used to index pictures, it gives a measurement to evaluate the tag quality for retrieval. 

\subsection{Generative models}

In \cite{Heymann:2008}, Heymann et al. define the social tag prediction problem. The purpose of social tag prediction is, given a set of tags applied to a set of objects by users, to predict whether or not a tag should be assigned to a particular object. Being able to predict applications of tags can lead to various enhancements, such as increase recall, inter-user agreement, tag disambiguation, bootstrapping and system suggestion. They collected tag data from the del.icio.us social bookmarking service and fetched the web pages for each saved bookmark. They analyse two methods, using page information and using solely tags. The first one is relevant in the situation of social bookmarking but does not apply in the case where the tagged objects are not web pages (e.g. images, songs, videos). They develop an entropy based metric which measures how much a tag is predictable. They extract association rules based on tag co-occurence and give measurements of their interest and confidence. They find that many tags do not contribute substantial additional information beyond page text, anchor text and surrounding hosts. Therefore these extra informations are good tag predictors. In the case of using only tags, predictability is related to generality in the sense that the more information is known about a tag (i.e. the more popular it is), the more predictable it is. They add that these measures could be used by system designers to improve system suggestion or tag browsing.

In \cite{Ramage:2008}, Ramage et al. compare two methods to cluster web pages using tag data. Their goal is to see whether tagging data can be used to improve web document clustering. This work is based on the \emph{clustering hypothesis} from information retrieval, "the associations between documents convey information about the relevance of documents to requests". The documents clusters are used to solve the problem of query ambiguity by including different clusters in search results.

In \cite{Griffiths:2004}, Griffiths et al. describe the latent dirichlet allocation method to extract topics from a collection of documents. The problem is to discover the set of topics that are used in a collection of documents. They treat each topic as a probability distribution over words, viewing a document as a probabilistic mixture of these topics. The resulting classification is a soft classification, meaning that each word occurs in multiple topics with different probabilities. The computation is a equivalent to a Markov chain Monte Carlo which converges to the target distribution.

Considering there is $T$ topics, the probability of the $i$th word in a given document can be written as :

\begin{equation}
	P(w_i) = \sum_{j=1}^{T}P(w_i|z_i=j)P(z_i=j)
\end{equation}

$z_i$ is a latent variable indicating from which the $i$th word was drawn from, $P(w_i|z_i=j)$ is the probability of the word $w_i$ under the $j$th topic and $P(z_i=j)$ the probability of choosing a word from topics j in the current document. The two main probability distributions are $P(w|z)$, which indicates which words are relevant to a topic and $P(z)$ indicates the importance of topics regarding a document. The computation involves two matrices $\theta$ and $\phi$. $\theta$ represents $T$ multinomial distributions over the $W$ words where $P(w|z=j) = \theta_w^{(j)}$ and $\phi$ represents $D$ multinomial distributions, where $D$ is the number of documents, over the $T$ topics such that for a document $d$, $P(z=j) = \phi_j^{(d)}$. The process is an expectation maximization of $P(w|\phi,\theta)$ using the previous equation. In this paper they actually use a much more efficient mechanism involving Gibbs sampling 

\section{Semantic Web}
The Semantic Web is a ``web of data" that enables machines to understand the semantics, or meaning, of information on the World Wide Web\footnote{\url{http://www.w3.org/wiki/SemanticWeb}}. One of the more basic things added through the concept of semantic web is adding machine-readable metadata about pages and how they are related to one another, enabling automated agents, such as search engines, access information more intelligently and perform tasks more efficiently on behalf of users. 

\subsection{Semantic Applications}
The key element of a semantic application is to determine the meaning of text and other data, and then create connections for users using the Web as platform. Data portability and connectability are keys to these new semantic apps. There are two approaches to develop these types of applications are: 
\begin{enumerate}
\item Bottom Up - involves embedding semantical annotations (meta-data) right into the data. 
\item Top down - relies on analyzing existing information; the ultimate top-down solution would be a fully blown natural language processor, which is able to understand text like people do.
\end{enumerate}
The linked data principles and associated best practices have significantly increased both the amount and the use of data in semantic form in recent years. 
\subsection{Ontology}
Ontologies play a large part in the concept of semantic web. During the course of the history of Western music, many have tried to formulate an answer to the question of the ontology of music. In order to distinguish between music and non-music, repeated attempts have been made to compile a list of essential properties of music along with the necessary and sufficient conditions. As such, ontology is also in the core of information science, representing knowledge as a set of concepts and describing relationships between those concepts. The concept of ontology has been adopted by Computer Science with a different meaning than it had in its origin. In philosophy, it reffered to essence of being. In general, ontology in Computer Science, is a way of representing a `common understanding' of a domain \cite{onto}. Ontology became a part of Computer Science as a result of requirement of knowledge representation which was indicated as crucial for the evolution of Artificial Intelligence, Software Engineering and Database disciplines. Computer Science models are constructed for small, reduced domains; if those models were hierarchical, then when modeling, we were looking for the primary elements of our reduced domain. That is the same goal that philosophical ontology has for the entire world.\\
Web ontology is a set of web identifiers for concepts and relationships in a domain. Different datasets can refer to when they deal with the same kind of thing using one of the properties of Web Ontology Language (OWL) namely, sameAs. A set of axioms characterising those concepts and relationships specified in RDF.

\subsubsection{Ontology and Software Architecture}
Ontologies share many common qualities with another computer science methodology, called object oriented programming. Object oriented programming (OOP) defines ‘classes’, which are used to define an object's behavior. A class has defined properties, which are slots for information storage for variables, as well as methods, which are functions that the class can do with its variables to produce new information or complete a specific task. Classes can be extended having child classes that share qualities (like methods or properties) of their parent classes. An instance of a class is called an object, once defined an object has their own variables and function cycle until they have served their purpose. Ontologies are very similar to this concept from knowledge mapping and logical storage perspective. In ontology, a class refers to sets or collections of knowledge concepts. Such a class has attributes (similar to property slots in OOP) as well as relations called superclasses (similar to parent classes in OOP) and various rules how information can be stored in those classes.\\ Unfortunately, the envisioned semantic web did not revolutionise the internet as expected since its inception. One of the major reason for this is that the commercial sector exploited the metadata part, and therefore, most of the search engines had to ignore the associated metadata and drive thier own to list unbiased results. There is no major search engine that relies on semantic web metadata stored on websites including Google. However, in database design and software architecture, the ontologies cannot be misused as in former case.\\
%http://waher.net/archives/932
The idea of free access is becoming popular with social networks, including Facebook, allow information to be fetched from its databases by other infosystems without having to rely on crawlers. This is done through Application Programming Interface (API) with information access is used these days by Facebook, MySpace and other major web networks to share information and make these platforms more useful for other systems on the internet. One of the main problems of APIs is that they are often built as layers and extracted information is in a non-standardized format. Ontology and web semantics have not revolutionalized such information access today, which means that any information system that accesses Facebook or Twitter needs to have their own profiles or set of rules in order to understand the information provided.\\
It has not helped that one of the more known methods of storing information in modern information systems, in language called Extensible Markup Language or XML, has been largely shunned by API’s due to it’s heavy footprint. From semantic web standpoint, the best part of XML has been the introduction of semantically more correct HTML, called XHTML. This means that today, most information systems store and share information in machine readable form, however in a way that requires hands-on development in majority of cases that are beyond simple snippets of information, such as RSS feeds (that are a standardized format of XML to share news, called Really Simple Syndication). While classes of ontologies and that of object oriented programming have many logical similiarities, the actual use of such concepts for information storage and database design is not common in most modern websites or information systems due to it being less time consuming and more productive from softwares standpoint to store information in the ways it needs to access it, without taking into account other systems. Should a need arise for other systems to access the information, a layer is built (usually together with the aforementioned API) that shares information in a certain way. While ontologies are not similar to the ways our brains store information, they are by far the most logical method of storing information, which can strongly help improve modern database designs and software architecture.

\subsubsection{FOAF Ontology}
Friend-of-a-friend or FOAF\footnote{\url{http://xmlns.com/foaf/spec/}} is a project devoted to linking people and information using the Web. Regardless of whether information is in people's heads, in physical or digital documents, or in the form of factual data, it can be linked. FOAF integrates three kinds of network: social networks of human collaboration, friendship and association; representational networks that describe a simplified view of a cartoon universe in factual terms, and information networks that use Web-based linking to share independently published descriptions of this inter-connected world. FOAF does not compete with socially-oriented Web sites; rather it provides an approach in which different sites can tell different parts of the larger story, and by which users can retain some control over their information in a non-proprietary format.\\ Foafing the Music is a music recommender system proposed by \cite{Celma2005} which uses Friend of a Friend (FOAF) and Rich Site Summary (RSS) vocabularies for recommending music to a user, depending on her musical tastes.

\subsubsection{Ontologies related to Music}
The most widely used Web Ontology for music-related data is Music Ontology. Music Ontology (MO) is based on other ontologies including Timeline ontology, Event ontology, Functional Requirements for Bibliographic Records, and Friend of a Friend. Music Ontology subsumes these ontologies to deal with music-related information including editorial data, music creation workflow, temporal annotations and event decomposition as well as creation of web identifiers for commonly used concepts in the music domain.\\
%http://ismir2009.dbtune.org/slides/
\textbf{Music Ontology Classification}
Music Ontology are classed in 3 different levels of descriptiveness:
\begin{itemize}
\item Level 1: Basic description of a music subject and aims at providing a vocabulary for simple editorial information (tracks/artists/releases, etc.)
\item Level 2: More advanced description of a music subject introducing the notions of Event and Time. It aims at providing a vocabulary for expressing the music creation workflow (composition, arrangement, performance, recording, etc.)
\item Level 3: The more advanced description of a music subject taking full advantage of ``event decomposition", able to express what happened precisely during a particular event, for example, what happened during a particular performance, what is the melody line of a particular work, etc.
\end{itemize}
Overtime many extensions of the MO have been made such as 
\begin{itemize}
\item Audio Feature Ontology (AF) which deals with publishing content-based audio descriptors.
\item Vamp Plugin Ontology describes audio feature extractors in RDF.
\item Vamp Transform Ontology Vamp feature extractor configuration (plugin parameters).
\item LV2 Plugin Schema: Describe audio processor plugins and their input/output requirements. 
\end{itemize}

%\section{Semantic Technologies}The technologies associated with the semantic web has many strengths and advantages over the web and XML-based application development. In order to define the conceptual framework and principles required to successfully apply semantic technologies to various domains. This includes a critical and up-to-date overview of the established, maturing, and newly developed standards and technologies related to W3C Semantic Web Layer Cake. This section covers the most lightweight and easily applied technologies, such as RDF(S) and SPARQL. There will also be extensive training on RDF, RDF schema-based inference, and SPARQL querying using Sesame’s Workbench Web UI.

\section{User Modeling}
User modeling is the process performed by an adaptive system in order to create and maintain an up-to-date user model. The system collects data about the user in two ways either by implicitly observing user interaction and/or by explicitly requesting direct input from the user. User modeling and adaptation are complementary to one another. The amount and the nature of the information represented in the user model depend to a large extent on the type of adaptation effect that the system has to deliver. The user modeling problem is often analyzed along three layers, by considering the nature and the form of information contained in the model as well as the methods of working with it, as \cite{D198571} suggests:
\begin{enumerate}
\item What is being modeled (nature)
\item How this knowledge is represented (structure)
\item How many different types of models are maintained (user modeling approaches)
\end{enumerate}
Information Retrieval and Filtering Systems develop user models to find items that are most relevant to user interests and then order them by pre-defined relevance criteria. The adopted user model typically represents the user's interests in terms of keywords, concepts or more complex metadata. User model is a representation of user's knowledge of the subject in relation to the expert-level domain knowledge e.g. Intelligent tutoring systems (ITS) attempt to select educational activities and deliver individual feedback according the user's level of knowledge. User models may rely on individual user features or generic users characteristics structured as stereotypes proposed in 1979 by Elaine Rich \cite{Elaine1979329}.

\subsection{User Modeling and Semantic Transparency}
A major challenge on the web is to link the distributed textual and multimedia resources. Hypertext is defined as a set of text nodes connected by links and Hypermedia is an extension of hypertext including multiple forms of media, such as text, video, audio, graphics, etc \cite{hyper}. Adaptive Hypermedia is a direction of research on the crossroad of hypermedia and user modeling \cite{journals/csur/BraBH99}. The semantic web main challenge is to associate with each web resource a semantics transparent for the computer systems to process the information as a logically structured and shared understanding of the concepts used within web applications to be exploited especially for the user or user communities benefits. Adaptive hypermedia systems build a user model and use it in order to adapt the hypertext to the user needs, providing him/her with personalized views of the hypermedia documents. The first techniques were borrowed from the data mining and machine learning domains; recently they were enhanced by integrating some semantic web techniques. Thus, many current adaptive hypermedia systems are mostly categorized as social web or Web 2.0 systems. The user model is a representation of information about an individual user developed by an adaptive system in order to provide users with personalized functionalities known as system's adaptation effect and could have many forms. When the user navigates from one resource to another, the system can manipulate the links (e.g., hide, sort, annotate) to provide adaptive navigation support. When the user reaches a particular resource, the system can present the content adaptively (adaptive content presentation). When the user searches for relevant information, the system can adaptively select and prioritize the most relevant items (personalized search). When the user accesses some resources, the system can recommend related items, according to his recent activity or according the activity of similar users (recommender systems).

